package com.gxc.string;

/**
 * 给定一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并让最终结果字符串的字典序最小
 * [举例]
 * str ="acbc"，删掉第一个'c’，得到"abc"，是所有结果字符串中字典序最小的。
 * str ="dbcacbca"，删掉第一个'b’、第一个'c'、第二个'c'、第二个'a，
 * 得到"dabc"是所有结果字符串中字典序最小的。
 *
 * 解法：
 * 词频表统计所有字符出现的次数，然后从头遍历字符串，遍历到相同的字符串时，词频表累计--，当累计到0时，
 * 记住当前位置，在当前位置中和之前选择一个字典序最靠前的字符X，X之后的字符串的X字符都替换为''（X的位置+1），
 * 继续遍历新的字符串
 */
public class LexicographicalOrder {

    public static void main(String[] args) {
        String str = "acbc";
        System.out.println(process(str));

        str = "dbcacbca";
        System.out.println(process(str));
    }

    public static String process(String str) {
        if (str == null || str.length()<2) return str;

        int[] map = new int[256];
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            map[chars[i]]++;
        }

        int minASCindex = 0;
        for (int i = 0; i < chars.length; i++) {
            //每次都计算当前字符中字典序最靠前的字符X
            minASCindex = chars[i] < chars[minASCindex]?i:minASCindex;
            if (--map[chars[i]] == 0) {
                break;
            }
        }
        return String.valueOf(chars[minASCindex]) +
                process(str.substring(minASCindex+1).replaceAll(String.valueOf(chars[minASCindex]), ""));
    }
}
